#include "common.h"

vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
	int n = mat.size();
	int m = mat[0].size();
	vector<vector<int>> sums(n + 1, vector<int>(m + 1, 0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + mat[i][j];
		}
	}

	vector<vector<int>> ans(n, vector<int>(m, 0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int r1 = max(0, i - k);
			int r2 = min(n, i + k + 1);
			int c1 = max(0, j - k);
			int c2 = min(m, j + k + 1);
			ans[i][j] = sums[r2][c2] - sums[r2][c1] - sums[r1][c2] + sums[r1][c1];
		}
	}
	return ans;
}